package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-24 11:25
 */
public class uniquePaths62 {

    /**62. 不同路径
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
     * 1、dp:dp[i][j]表示从（0，0）到达（i，j）的最多路径
     *       dp[i][j]=dp[i-1][j]+dp[i][j-1]
     * 2、组合数学：从左上角到右下角的过程中，我们需要移动 m+n-2次，其中有 m-1 次向下移动，n-1 次向右移动。因此路径的总数，就等于从 m+n-2次移动中选择 m-1 次向下移动的方案数
     *   计算（m+n-1）!/(m-1)!(n-1)!
     * */
    public int uniquePaths1(int m, int n) {
        int[][] dp=new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0]=1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i]=1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

    public int uniquePaths(int m, int n) {
        long res=1;
        for (int x = n,y=1; y < m; x++,y++) {
            res=res*x/y;
        }
        return (int) res;
    }

}
